// Copyright (c) 2006, Inc.
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
//
// Author: arvin.chen
//
//

#ifndef ALGORITHM_SORT_SHELL_H_
#define ALGORITHM_SORT_SHELL_H_

#ifndef ALGORITHM_SORT_BASE_H_
#include "algorithm/sort/base.h"
#endif

namespace algorithm {
	namespace sort {
		
		template<typename T>
		class Shell : public Base<T> {
		public:

			/**
			* Construction
			*
			* @param
			* @return
			*/
			Shell() :
				Base<T>::Base(kShell)
			{
				
			}

			/**
			* Destruction
			*
			* @param VOID
			* @return
			*/
			~Shell()
			{

			}

			/**
			* sort
			*
			* @param T arr[]
			* @param int len
			* @return T
			*/
			virtual T* sort(T arr[], int len)
			{
				if (nullptr == arr || 1 >= len) return arr;
				// Sort each group with an interval of h, at the beginning h = n / 2;
				for (int h = len / 2; h > 0; h /= 2) {
					//Insertion sort for each partial group
					for (int i = h; i < len; i++) {
						// Insert arr[i] into the correct position of the group
						InsertI(arr, h, i);
					}
				}
				return arr;
			}

		protected:
			/**
			* Assignment
			*
			* @param const Shell& cbase
			* @return Shell&
			*/
			Shell& operator=(const Shell& cbase);

			/**
			* Copy Construction
			*
			* @param const Shell& cbase
			* @return
			*/
			Shell(const Shell& cbase);

		private:


			/**
			* InsertI
			* Insert arr[i] into the correct position of the group
			* The group of arr[i]] is... arr[i-2*h], arr[i-h], arr[i+h] ...
			*
			* @param T arr[]
			* @param int h
			* @param int i
			* @return void
			*/
			void InsertI(T arr[], int h, int i) {
				T temp = arr[i];
				int k;
				for (k = i - h; k >= 0 && temp < arr[k]; k -= h) {
					arr[k + h] = arr[k];
				}
				arr[k + h] = temp;
			}

		public:
		protected:
		private:

		};
	} // namespace algorithm 
} // namespace sort


#endif  // ALGORITHM_SORT_SHELL_H_
